import typing
li = []
sorted()
li.sort()
def merge(li, low, mid, high):
    """

    :param li:
    :param low:左边排序的开头
    :param mid: 右边排序的开头
    :param high: 长度
    :return:
    """
    new_li = []
    right_start = mid
    left_start = low
    while True:
        if li[left_start] < li[right_start]:
            new_li.append(li[left_start])
            left_start += 1
        else:
            new_li.append(li[right_start])
            right_start += 1
        if right_start > high:
            new_li.extend(li[left_start:mid])
            break
        if left_start > mid:
            new_li.extend(li[right_start:])
            break

    li[low:high + 1] = new_li


li = [3, 5, 7, 9, 1, 4, 6]
print(merge(li, 0, 4, len(li) - 1))
# print(li)
